/*
 * @lc app=leetcode.cn id=105 lang=cpp
 * @lcpr version=30204
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode *_buildTree(vector<int> &preorder, vector<int> &inorder, int &prei, int inbegin, int inend)
    {
        // 构建当前根节点
        TreeNode *root = new TreeNode(preorder[prei]);

        int rooti = inbegin;
        // 找到根节点在中序数组中的位置
        while (rooti <= inend)
        {
            if (inorder[rooti] == preorder[prei])
                break;
            else
                rooti++;
        }

        // 递归构建左子树
        if (inbegin <= rooti - 1)
            root->left = _buildTree(preorder, inorder, ++prei, inbegin, rooti - 1);
        else
            root->left = nullptr;
            
        // 递归构建右子树
        if (rooti + 1 <= inend)
            root->right = _buildTree(preorder, inorder, ++prei, rooti + 1, inend);
        else
            root->right = nullptr;

        return root;
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        int prei = 0;
        int inbegin = 0;
        int inend = inorder.size() - 1;

        return _buildTree(preorder, inorder, prei, inbegin, inend);
    }
};
// @lc code=end

/*
// @lcpr case=start
// [3,9,20,15,7]\n[9,3,15,20,7]\n
// @lcpr case=end

// @lcpr case=start
// [-1]\n[-1]\n
// @lcpr case=end

 */
